2018.4.20 leetcode DP看的头大...

2018.4.20## Array - 628. Maximum Product of Three Numbers

题目详情

Given an integer array, find three numbers whose product is maximum and output the maximum product.

找到一列数组中，乘积结果最大的三个值的乘积。每个值范围是[1000,-1000]

Example:

Input: [1,2,3,4]
Output: 24

思路

• 找出最大前三位值和最小前两位值
• 前三大值的乘积 和 最大值和前两小值的乘机

具体代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumProduct = function(nums) {
    let min1 = min2 = 1001
        max1 = max2 = max3 = -1001
    for(let i = 0, len = nums.length; i < len; i++) {
        if(nums[i] > max1) {
            max3 = max2
            max2 = max1
            max1 = nums[i]
        } else if(nums[i] > max2) {
            max3 = max2
            max2 = nums[i]
        } else if(nums[i] > max3) {
            max3 = nums[i]
        }
        
        if(nums[i] < min1) {
            min2 = min1
            min1 = nums[i]
        } else if(nums[i] < min2) {
            min2 = nums[i]
        }
    }
    return Math.max(max1*max2*max3, min1*min2*max1)
};

---

Array - 746. Min Cost Climbing Stairs

题目详情

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

有一个楼梯，每次可以走1层或者2层，cost数组表示每一层所需要花费的值。可以从第一层或者第二层开始。求，到达顶端所花费大的最小的值。

Example:

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]

Output: 6

思路

• 让dp[i]成为第i层楼梯的最低成本。
• dp的转换方程 dp[i] = cost[i] + Math.min(dp[i-1], dp[i-2])

具体代码

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function(cost) {
    let len = cost.length;
    let dp = []
    dp[0] = cost[0]
    dp[1] = cost[1]
    for(let i = 2; i < len; i++) {
        dp[i] = cost[i] + Math.min(dp[i-2], dp[i-1])
    }
    
    return Math.min(dp[len-2], dp[len-1])
};